Point-based surface models define a surface of a 3D graphics object by a set of sample points. Point-based rendering generates a continuous image of the discrete sampled surface points. The points on the surface are commonly called surface elements or “surfers” to indicate their affinity with picture elements (pixels) and volume elements (voxels).
A point-based representation has advantages for graphics models with complex topologies in rendering applications where connectivity information is not required or available, or for fusion of data from multiple sources, see for example, Levoy et al., “The Use of Points as Display Primitives,” Technical Report TR 85-022, The University of North Carolina at Chapel Hill, Department of Computer Science, 1985, Zwicker et al., “Surface Splatting,” SIGGRAPH 2001 Proceedings, pp. 371–378, 2001, and U.S. Pat. No. 6,396,496 issued to Pfister et al. on May 28, 2002 “Method for modeling graphical objects represented as surface elements,” incorporated herein by reference.
Point-based models can be acquired directly using 3D scanning techniques, or by conversion from polygon models with textures, see Levoy et al., “The Digital Michelangelo Project: 3D Scanning of Large Statues,” SIGGRAPH 2000 Proceedings, pp. 131–144, 2000, and Pfister et al., “Surfels: Surface Elements as Rendering Primitives,” SIGGRAPH 2000 Proceedings, pp. 335–342, 2000.
Most prior art point-based rendering methods have focused on efficiency and speed. Some of those methods use OpenGL and hardware acceleration to achieve interactive rendering performances of two to five million points per second, see Rusinkiewicz et al., “QSplat: A Multiresolution Point Rendering System for Large Meshes, SIGGRAPH 2000 Proceedings, pp. 343–352, 2000, and Stamminger et al., “Interactive Sampling and Rendering for Complex and Procedural Geometry,” Proceedings of the 12th Eurographics Workshop on Rendering, pp. 151–162, 2001.
However, none of those techniques supports anti-aliasing for models with complex surface textures. Recently, Zwicker et al. described elliptical weighted average (EWA) surface splatting, see Zwicker et al. “Surface Splatting,” SIGGRAPH 2001 Proceedings, pp. 371–378, 2001, and U.S. patent application Ser. No. 09/842,737 “Rendering Discrete Sample Points Projected to a Screen Space with a Continuous Resampling Filter,” filed by Zwicker et al., on Apr. 26, 2001, incorporated herein by reference.
Those methods uses anisotropic texture filtering and an image-space formulation of an EWA texture filter adapted for irregular point samples, see Greene et al., “Creating Raster Omnimax Images from Multiple Perspective Views Using the Elliptical Weighted Average Filter,” IEEE Computer Graphics & Applications, 6(6):21–27, 1986, and Heckbert, “Fundamentals of Texture Mapping and Image Warping,” Master's Thesis, University of California at Berkeley, Department of Electrical Engineering and Computer Science, 1989.
However, a software implementation of EWA surface splatting only achieves a rendering performance of up to about 250,000 points per second.
Polygon and point primitives can also be combined into efficient rendering systems that select one or the other based on image space projection criteria, see Chen et al., “POP: A Hybrid Point and Polygon Rendering System for Large Data,” Proceedings of IEEE Visualization, pp. 45–52, 2001, and Cohen et al., “Hybrid Simplification: Combining Multi-Resolution Polygon and Point Rendering,” Proceedings of IEEE Visualization, pp. 37–44, 2001. Both of those systems make use of graphics hardware to achieve real-time performance for reasonably complex models. However, neither system handles surface textures, and the introduction of connectivity information further diminishes the advantages of pure point-sampled models.
Image Space EWA Splatting
In the image space EWA splatting framework as described by Zwicker et al., objects are represented by a set of irregularly spaced points {Pk} in three dimensional object space without connectivity information, in contrast with polygon or triangle models which do contain adjacency or connectivity information.
Each zero-dimensional point is associated with a location, a surface normal, a radially symmetric basis function rk, and scalar coefficients wrk, wgk, wbk that represent continuous functions for red, green, and blue color components. The basis functions rk are reconstruction filters defined on locally parameterized domains. Hence, the functions define a continuous texture function on the model's surface as represented by the discrete points.
FIG. 1 shows a local parameterization 101 from 3D object space 102 to 2D image space 103. The color of a neighborhood of any point Q 104 with local coordinates u is evaluated by accumulating the basis functions rk 105 yielding a continuous texture function fc(u) as the weighted sum
                                                        f              c                        ⁡                          (              u              )                                =                                    ∑                              k                ∈                N                                                                                  ⁢                                          w                k                            ⁢                                                r                  k                                ⁡                                  (                                      u                    -                                          u                      k                                                        )                                                                    ,                            (        1        )            where uk is the local coordinate of each point Pk.
In the ideal resampling framework described by Heckbert et al., rendering the texture function fc(u) yields a continuous output function gc(x) in image space that respects the Nyquist criterion of the output pixel grid. Thus, aliasing artifacts are avoided. The rendering process includes the following steps.
First, the texture function fc(u) is warped to image space using a local affine mapping of the perspective projection at each point. Then the continuous image space signal is band-limited by convolving it with a prefilter h, yielding the output function gc(x), where x are image space coordinates. After rearranging the mathematical expressions, the output function can be expressed as a weighted sum of image space resampling filters ρk x:ρk(x)=(r′k{circle around (x)}h) (x−mk(uk)).  (3)where
                                                        g              c                        ⁡                          (              x              )                                =                                    ∑                              k                ∈                N                                                                                  ⁢                                          w                k                            ⁢                                                ρ                  k                                ⁡                                  (                  x                  )                                                                    ,                            (        2        )            
Here, the resampling filter ρkx is written as a convolution of a warped basis function rk(x)=rk(x)(m−1(x), and the pre-filter h(x).
To simplify the evaluation of ρk at each point uk, a local affine approximation                x=mk(u) of the projective mapping x=m(u) from the local surface parameterization to image space is used. The local affine approximation mk ismk(u)=xk+Jk·(u−uk),  (4)        
 given by the Taylor expansion of m at uk, truncated at the linear term:
where xk=m(uk) and the Jacobian
      J    k    =                              ∂          m                          ∂          u                    ⁢              (                  u          k                )              ∈                  ℝ                  2          ×          2                    .      
In the EWA framework, elliptical Gaussians are selected as basis functions rk and as pre-filters h because of their unique properties. Gaussians are closed under affine mappings and convolution. Hence, the resampling filter ρk can be expressed as an elliptical Gaussian, as described below. A 2D elliptical Gaussian Gv (x) with variance matrix VεR2×2 is defined as
                    G        V            ⁡              (        x        )              =                  1                              2            ⁢            π                    |          V          ⁢                      |                          1              2                                          ⁢              ⅇ                              -                          1              2                                ⁢                      x            T                    ⁢                      V                          -              1                                ⁢          x                      ,
where |V| is the determinant of V. The variance matrices of the basis functions rk and the low-pass filter h are defined with Vkk and Vh, hence rk=GVkr and h=GVh, respectively.
Note that a typical choice for the variance of the low-pass filter is the identity matrix I. By substituting the Gaussian basis function and prefilter in Equation (3), a Gaussian resampling filter
                                                        ρ              k                        ⁡                          (              x              )                                =                                    1                              |                                  J                  k                                      -                    1                                                  |                                      ⁢                                          G                                                                            J                      λ                                        ⁢                                          V                      λ                      r                                        ⁢                                          J                      λ                      T                                                        +                  I                                            ⁡                              (                                  x                  -                                                            m                      k                                        ⁡                                          (                                              u                        k                                            )                                                                      )                                                    ,                            (        5        )            
can be obtained, which is called an image space EWA resampling filter, for additional details see Zwicker et al.
Image space filters are suitable for software implementations. However, hardware graphics engines cannot determine such filters directly in image space. Hence the rendering performance is severely degraded, e.g., by an order of magnitude or more, as indicated above.
Therefore, it is desired to provide a rendering system that interactively renders complex point-based models with arbitrary surface textures at a highest possible quality. The rendering system should take advantage of advances in PC graphics hardware, namely, the ever increasing performance of graphic processing units (GPUs), and programmable shading. The system should also provide anisotropic texture filtering.